Data storage devices, such as disk drives and solid state drives, can use “logical block address (LBA) indirection” to store user data on non-volatile media, such as a disk surface or Flash memory, wherein data for LBAs are not typically stored in the same physical location each time they are written. For example, if data is written to LBA 0, it may be stored in physical location 0 on the non-volatile media. But if it is written again later, it may be stored in a new physical location, such as physical location 20. Thus, with LBA indirection, a physical location on the non-volatile media may contain data for any LBA. When a host rewrites a particular LBA on a storage device with LBA indirection, the older copy of the LBA and associated user data is not overwritten or erased. The more recent copy of the LBA is written into a new physical location, thereby invalidating the user data stored in the old physical location.
In order to reuse old physical locations containing invalid data, a region of the non-volatile media containing the old physical locations can be erased. However, before erasing the region containing the invalid data, a garbage collection operation is typically performed to identify and migrate into another region any valid data that is stored in physical locations located in the same region of the non-volatile media as the invalid data.
There is, therefore, a need to efficiently identify valid user data on non-volatile media of a data storage device for migration during a garbage collection operation.